// https://leetcode.cn/problems/super-ugly-number/
// Created by ade on 2022/11/11.
// 超级丑数 是一个正整数，并满足其所有质因数都出现在质数数组 primes 中。
//
//给你一个整数 n 和一个整数数组 primes ，返回第 n 个 超级丑数 。
//
//题目数据保证第 n 个 超级丑数 在 32-bit 带符号整数范围内。
//
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>

using namespace std;

class Solution {
public:
    // 多路并归
    int nthSuperUglyNumber1(int n, vector<int> &primes) {
        if (n <= 1) return 1;
        unordered_map<int, int> m = {};
        for (auto &i:primes) m[i] = 1;
        vector<long> dp(n + 1, 0);
        dp[1] = 1L;
        for (int i = 2; i <= n; i++) {
            dp[i] = INT_MAX;
            for (auto &j:m)
                dp[i] = min(dp[i], (long) j.first * dp[j.second]);
            for (auto &j:m)
                if ((long) j.first * dp[j.second] == dp[i]) j.second++;
        }

        return dp[n];
    }

    // 最小栈
    int nthSuperUglyNumber(int n, vector<int> &primes) {
        if (n <= 1) return 1;
        priority_queue<long, vector<long>, greater<long>> pq;
        pq.push(1);
        unordered_set<long> myS = {};
        int top = 0;
        for (int i = 0; i < n; i++) {
            top = pq.top();
            while (myS.count(top) > 0) {
                pq.pop();
                top = pq.top();
            }
            myS.insert(top);
            pq.pop();
            for (auto &i:primes)
                pq.push((long) i * top);
        }
        return top;
    }

};

int main() {
    Solution so;
    vector<int> primes = {2, 7, 13, 19};
    //3,5,6,7,10,11,12,14,19,20,22,23,24,28
    cout << so.nthSuperUglyNumber(12, primes);
    return 0;
}

